Graph-based signal processing merges algebraic and spectral graph theoretic concepts with computational harmonic analysis to process signal using graphs.
An undirected graph G=(V, E) includes a set of nodes V={1, 2, . . . , N} connected by a set of edges E:{(i,j,wij)}, where (i, j, wij) the edge between nodes i and j having weights wij. An adjacency matrix W of the graph is an N×N matrix. A degree di of a node i is a sum of edge weights connected to node i.
A degree matrix D is a diagonal matrix: diag{d1, d2, . . . , dN}. A combinatorial Laplacian matrix is :=D−W. The normalized Laplacian matrix L:=D−1/2D<1/2 is a symmetric positive semi-definite matrix. The matrix L has an eigendecomposition L=U Λ Ut, where Ut is a graph Fourier transform {u1, u2, . . . , uN} that is composed of an orthogonal set of eigenvectors, and Λ=diag{λl, . . . λN} is a corresponding eigenvalue matrix. In the above notation Ut, the superscript t indicated a transpose of the matrix U.
The eigenvectors and eigenvalues of the Laplacian matrix provide a spectral interpretation of signals represented by the graph. The eigenvalues can be treated as graph frequencies that are always in the interval [0,2] on a real line.
Graph Fourier transform (GFT) and Graph Spectral Filter (GSF)
A signal {circumflex over (x)} is normalized as x=D1/2 {circumflex over (x)}. A graph Fourier transform (GFT) is defined as a projection of the normalized signal x onto the eigenvectors U of the graph:{tilde over (x)}:=Utx,   (1)where {tilde over (x)} are the GFT coefficients. The inverse transform isx:=U{tilde over (x)},   (2)
The signal x is normalized because the eigenvector U is defined, over the normalized Laplacian matrix L. By definition, W, D and  can be regarded as operators over the unnormalized signal {circumflex over (x)}. The unnormalized signal {circumflex over (x)} can also be processed asD½LD½{circumflex over (x)}=D½UΛUtD½{circumflex over (x)}=D½UΛ(Utx).
It is meaningful to analyze a transform by applying Ut over the normalized signal x, which is the GFT. The normalizer D1/2 is determined in the context of the graph G.
Normalization of an unnormalized signal is represented asx:=D1/2{circumflex over (x)},   (3)and the denormalization is represented as{circumflex over (x)}:=D−1/2x,   (4)
With the GSF and the inverse GSF, the signal x can be converted between a spatial domain and a graph spectral domain. The GSF is defined by the graph G, its adjacency matrix W, or the Laplacian matrix L.
As described later, any graph G has a corresponding filter design. Hence, a graph can be named by its corresponding filter name, e.g. bilateral graph filter refers to a graph with weights defined as bilateral coefficients.
Defining the graph does not change signal processing because it can be assumed as an equivalent representation of a conventional filter. However, with the GFT based on the graph G, a new spectral domain is defined. It is possible to perform the GST in the graph spectral domain as defined by{tilde over (x)}out:=H1(Λ){tilde over (x)}in,   (5)where H1(Λ)=diag (h1(λi)). Or in another form:{tilde over (x)}out(λi):=hi(λi){tilde over (x)}in(λi),where h1(λi) can be a lowpass highpass or any other type of filter in the graph spectral domain.
Correspondingly, in the spatial domain, the GSF includes the GFT transform, the GSF filtering, and the inverse GFT transform as described below:xout=UH1(Λ)Utxin:=H()xin,   (7)
The filtering kernels in the spatial domain and spectral domain are linked asH()=UH1(Λ)Ut   (8)or H1(Λ)=UtH()U   (9)
In the above equations, the GSF and inverse GSF are defined over normalized signals. For unnormalized signals, the eigendecomposition may be performed over a combinatorial Laplacian matrix, which has different eigenvectors and eigenvalues.
Considerations for GSF Filter Design
The GSF can be used for image filtering and other applications. To apply graph based signal processing described above to design a graph based image filter, the following steps can be performed.
First, a graph is constructed. Then, a graph spectral filter H1 is designed in terms of the graph. The design of the graph can use any known image filter F. For an input image {circumflex over (x)}in, the output image {circumflex over (x)}out is a weighted average of pixels
                                                                        x                ^                            out                        ⁡                          [              j              ]                                =                                    ∑              i                                                                    ⁢                                                  ⁢                                                            w                  ij                                                                      ∑                    i                                                                                                  ⁢                                                                          ⁢                                      w                    ij                                                              ⁢                                                                    x                    ^                                    in                                ⁡                                  [                  i                  ]                                                                    ,                            (        10        )            where wij are the weighting coefficients between pixel i and j. For example, a bilateral graph G has bilateral weights w defined by:
      w    ij    =            exp      ⁡              (                  -                                                                                                          p                    i                                    -                                      p                    j                                                                              2                                      2              ⁢                                                          ⁢                              σ                s                2                                                    )              ⁢                  exp        ⁡                  (                      -                                                            (                                                                                    x                        in                                            ⁡                                              [                        i                        ]                                                              -                                                                  x                        in                                            ⁡                                              [                        j                        ]                                                                              )                                2                                            2                ⁢                                                                  ⁢                                  σ                  r                  2                                                              )                    .      
The corresponding graph is defined as G=(V, E) where the nodes V represent the pixels of the input image and the edges E represent the weighting (filtering) coefficients between two pixels i and j. The adjacency matrix W of the graph is W=[wij]. With these definitions, the degree matrix D, the combinatorial Laplacian matrix , the normalized Laplacian matrix L, the eigenvalue matrix Λ, and the eigenvalue matrix U can be determined.
Identity Graph Spectral Filter
In an identity graph spectral filter (iGSF), the signal is unchanged in the graph spectral domain. That is, the signal filtered by iGSF is
                                                                                          x                  ^                                out                            =                            ⁢                                                D                                      -                    1                                                  ⁢                W                ⁢                                                      x                    ^                                    in                                                                                                        =                            ⁢                                                D                                      -                                          1                      2                                                                      ⁢                                                                            D                                              -                                                  1                          2                                                                                      ⁢                                          WD                                              -                                                  1                          2                                                                                                      ︸                                ⁢                                  D                                      1                    2                                                  ⁢                                                                            x                      ^                                        in                                    (                  12                  )                                                                                                        =                            ⁢                                                D                                      -                                          1                      2                                                                      ⁢                                                      (                                          I                      -                      L                                        )                                    ︸                                ⁢                                  D                                      1                    2                                                  ⁢                                                                            x                      ^                                        in                                    (                  13                  )                                                                                        (        11        )                                          ⇒                                    D                              1                2                                      ⁢                                          x                ^                            out                                      =                                            (                              I                -                L                            )                        ︸                    ⁢                      D                          1              2                                ⁢                                                    x                ^                            in                        .                                              (        14        )            
Eqn. (14) can be rewritten asxout=(I−L)xin   (15)where xin is the normalized input image, and xout is the normalized output image, and I is an identity matrix.
The normalization can be used to define the image filtering in terms of the non-negative definite matrix L, and thus has a spectral interpretation. The normalization also ensures that a constant signal, when normalized, is an eigenvector of L associated with zero eigenvalue.
By comparing Eqn. (7) and Eqn. (15) H for an identity GSF can be represented as:H=I−L   (16)
In the frequency domain, H1 for the identity GSF can be represented as:
                                                                        H                1                            =                            ⁢                                                U                  t                                ⁢                HU                                                                                        =                            ⁢                                                                    U                    t                                    ⁡                                      (                                          I                      -                      L                                        )                                                  ⁢                                  U                  (                  18                  )                                                                                                        =                            ⁢                                                                    U                    t                                    ⁡                                      (                                          I                      -                                              U                        ⁢                                                                                                  ⁢                        Λ                        ⁢                                                                                                  ⁢                                                  U                          t                                                                                      )                                                  ⁢                                  U                  (                  19                  )                                                                                                        =                            ⁢                              I                -                                  Λ                  (                  20                  )                                                                                        (        17        )            
As shown in FIG. 1, the above equation is the spectral response of an identity GSF as a function of eigenvalues λ.
In an example application used to describe the embodiments, the signals are images, for example, noisy images to be enhanced by reducing noise. Specifically, the noisy images can be depth images.
To better understand the identity GSF, Ĥ and Ĥ1 are detailed in the unnormalized domain:
                                                                        H                ^                            =                            ⁢                                                                    D                                          -                                              1                        2                                                                              ⁡                                      (                                          I                      -                      L                                        )                                                  ⁢                                  D                                      1                    2                                                                                                                          =                            ⁢                                                D                                      -                                          1                      2                                                                      ⁢                                                      HD                                          1                      2                                                        (                  22                  )                                                                                        (        21        )                                                                                                      H                  ^                                1                            =                            ⁢                                                U                  t                                ⁢                                  H                  ^                                ⁢                U                                                                                        =                            ⁢                                                                    U                    t                                    ⁡                                      (                                                                                            D                                                      -                                                          1                              2                                                                                                      ⁡                                                  (                                                      I                            -                            L                                                    )                                                                    ⁢                                              D                                                  1                          2                                                                                      )                                                  ⁢                                  U                  (                  24                  )                                                                                                                        =                                ⁢                                                      U                    t                                    ⁢                                                            D                                              -                                                  1                          2                                                                                      ⁡                                          (                                              I                        -                                                  U                          ⁢                                                                                                          ⁢                          Λ                          ⁢                                                                                                          ⁢                                                      U                            t                                                                                              )                                                        ⁢                                      D                                          1                      2                                                        ⁢                                      U                    (                    25                    )                                                              ⁢                                                                                                                      =                            ⁢                                                U                  t                                ⁢                                  D                                      -                                          1                      2                                                                      ⁢                                  U                  ⁡                                      (                                          I                      -                                                                                          ⁢                      Λ                                        )                                                  ⁢                                                                  ⁢                                  U                  t                                ⁢                                  D                                      1                    2                                                  ⁢                                  U                  (                  26                  )                                                                                                        =                            ⁢                                                                                          U                      t                                        ⁢                                          D                                              -                                                  1                          2                                                                                      ⁢                    U                                                        ︸                    C                                                  ⁢                                                      H                    1                                                        ︸                    B                                                  ⁢                                                                            U                      t                                        ⁢                                          D                                              1                        2                                                              ⁢                    U                                                        ︸                    A                                                  ⁢                                  (                  27                  )                                                                                        (        23        )            
From Eqn. (27), the filtering kernel in frequency domain is composed of three parts.
In Part. A, the spectral signal is first inverse transformed to the spatial domain such that the normalizer is applied and then transformed to spectral domain.
The signal fed to part B is in the spectral domain, and Part B is given by H1=I−Λ in case of the iGSF. After filtering by H1 in the graph-spectral domain, the spectral signal is then fed to Part. C.
Part C inverse trans onus to the spatial domain such that the denormalizer is applied and then transformed hack to frequency domain.
The design of the graph G is an important task, because xout=UH1Utxin, U and Λ are all determined by the selected graph G.
Following the graph selection, another issue is to design the GSF filter H1 to satisfy requirements for particular applications. H1 can be a lowpass, highpass or other types of filter. This disclosure addresses the filter parameter estimation problem for the GSF filter.
High-Pass Graph Filter
In a high-pass graph Filter, the graph filter H is used to extract high frequency components from an input image xout=Hxin=UH1Utxin.
Overview of Graph Based Interpolation
Conventional methods for interpolating signals defined on graphs include a method based on sampling theorem for bandlimited graph signals, and a method based on regularization.
Interpolation Based on Graph Sampling Theorem
In the sampling theorem method, data interpolation is formulated as a signal reconstruction problem on a graph, where a graph signal is defined as the information associated with each node, e.g., scalar or vector values mapped to the set of vertices and edges of the graph. In the graph sampling method, w stands for the weight between nodei and j. The known set is S, and the unknown set is Sc=V−S. A signal is bandlimited to the graph frequency band [0, ω) on a graph G when its GFT Ut has support only at frequencies [0, ω). The space of ω-bandlimited signals is called the Paley-Wiener space and is denoted by PWω(G),
The partially known graph function can be formulated as a downsampled-upsampled (DU) signal. In a regular signal domain, the original signal is recovered from its DU signal by applying a low-pass filter. Similarly, in the graph domain, a low-pass filters can be designed to recover the original graph signal from the DU signal. An optimal cut-off frequency ω* can be determined asω*=σmin,   (28)where σ2min is a smallest singular value of (2)Sc.
Given the cut-off frequency ω*, the reconstruction of the graph signal is done by a least-square (LS) projection of the corresponding DU signal onto the PWω(G) space. Let k be the number of eigenvalues of the Laplacian matrix  less than ω*.
The ω-bandlimited signal can be written, under appropriate permutation, as:
                              x          =                                    [                                                                                          x                      ⁡                                              (                        S                        )                                                                                                                                                        x                      ⁡                                              (                                                  S                          c                                                )                                                                                                        ]                        =                                          [                                                                                                                              u                          1                                                ⁡                                                  (                          S                          )                                                                                                                                                              u                          2                                                ⁡                                                  (                          S                          )                                                                                                            …                                                                                                                u                          k                                                ⁡                                                  (                          S                          )                                                                                                                                                                                                  u                          1                                                ⁡                                                  (                                                      S                            c                                                    )                                                                                                                                                              u                          2                                                ⁡                                                  (                                                      S                            c                                                    )                                                                                                            …                                                                                                                u                          k                                                ⁡                                                  (                                                      S                            c                                                    )                                                                                                                    ]                            ⁡                              [                                                                                                    α                        1                                                                                                                                                α                        2                                                                                                                        ⋮                                                                                                                          α                        k                                                                                            ]                                                    ⁢                                  ⁢                                            Let              ⁢                                                          ⁢              α                        =                                          [                                                      α                    1                                    ,                                      α                    2                                    ,                  …                  ⁢                                                                          ,                                      α                    k                                                  ]                            t                                ,                                          ⁢          and                                    (        29        )                                          [                                                                                          u                    1                                    ⁡                                      (                    S                    )                                                                                                                    u                    2                                    ⁡                                      (                    S                    )                                                                              …                                                                                  u                    k                                    ⁡                                      (                    S                    )                                                                                                                                            u                    1                                    ⁡                                      (                                          S                      c                                        )                                                                                                                    u                    2                                    ⁡                                      (                                          S                      c                                        )                                                                              …                                                                                  u                    k                                    ⁡                                      (                                          S                      c                                        )                                                                                ]                =                  [                                                                                          (                                          U                      k                                        )                                    S                                                                                                                          (                                          U                      k                                        )                                                        S                    c                                                                                ]                                    (        30        )            where Uk is the matrix containing the first k eigenvectors, and (Uk)s is the sub-matrix of Uk containing rows corresponding to the set S. Then, α can be obtained by determining the least square solution to:x(S)=(Uk)sα  (31)
That is,α=(Uk)S†x(S)   (32 )where † indicates a pseudo-inverse of the matrix.
Hence, the unknown signal values arex(Sc)=(Uk)Scα  (33)x(Sc)=(Uk)Sc(Uk)S†x(S)   (34)
Interpolation Based on Regularization
In the regularization method, the data interpolation is formulated as a regularization problem
                                          x            .                    =                                                                      arg                  ⁢                                                                          ⁢                  min                                x                            ⁢                                                          ⁢                                                                                                              J                      ⁡                                              (                                                                              x                            du                                                    -                          x                                                )                                                                                                  2                                                  ︸                  A                                                      +                          ρ              ⁢                                                                                        Hx                                                        2                                                  ︸                  B                                                                    ⁢                                  ⁢                              where            ⁢                                                  ⁢            J            ⁢                          :                        ⁢                                                  ⁢                          ℝ              N                                →                      ℝ            M                                              (        35        )            denotes a downsampling operator. M is a size of an known subset of samples, and N is a size of a full set of samples. J can be represented by an appropriate permutation:JM×N=(IM×M|0M×(N−M))M×N   (36)and xdu can be in the following form with appropriate permutationxdu=[x(S)t, 0(Sc)t]t,
Then, H is a high pass regularization graph filter. Part A in equation 35 is a data-fitting term that determines the error between the reconstructed signal and the original signal at the known samples, and part B is the Euclidean norm of the output of a highpass graph filter H.
The solution is
                                                                        x                .                            =                            ⁢                                                                    (                                                                                            J                          t                                                ⁢                        J                                            +                                              ρ                        ⁢                                                                                                  ⁢                                                  H                          t                                                ⁢                        H                                                              )                                                        -                    1                                                  ⁢                                  x                  du                                                                                                        =                            ⁢                                                                    U                    ⁡                                          (                                                                                                    U                            t                                                    ⁢                                                      J                            t                                                    ⁢                          JU                                                +                                                  ρ                          ⁢                                                                                                          ⁢                                                      H                            1                            t                                                    ⁢                                                      H                            1                                                                                              )                                                                            -                    1                                                  ⁢                                  U                  t                                ⁢                                                      x                    du                                    (                  38                  )                                                                                        (        37        )            
Iterative methods can be used to solve the least square problem at a reduced complexity.